Bazy danych są obecnie jedną z najważniejszych dziedzin informatyki, pozwalając na przechowywanie i przetwarzanie masywów danych. Obecnie coraz popularniejsze stają się rozwiązania baz pamięciowych baz danych (ang. in-memory), które nie przechowują danych na dysku, lecz w pamięci operacyjnej systemu, pozwalając na szybszy dostęp do nich.

Mimo wszystko, implementacja takich baz może opierać się na różnch strukturach, które charakteryzują się różną wydajnością poszczególnych operacji takich jak odczyt, zapis czy modyfikacja.

Z tego też powodu wybraliśmy 3 różne struktury pamięciowe, a następnie zmieżyliśmy czas poszczególnych wykonywania wielokrotnego zapisu, odczytu, odczytu sekwencyjnego, modyfikacji oraz usuwania dla baz danych o różnej wielkości oraz zajętości.

Na podstawie wyników jesteśmy w stanie stwierdzić, że struktury oparte na słowniku pozwalają na najwydajniejsze wstawianie oraz odczyt danych, a te na T-Drzewie na odczyt sekwencyjny, zapewniając bardzo dobre wyniki względem pozostałych struktur.

Kod projektu dostępny jest pod adresem: https://github.com/Cheriit/memory-structures-performance

1 Wprowadzenie

Wstęp do pracy opisujący motywacje, wybrany problem oraz cel pracy.

1.1 Motywacje i opis problemu

Motywem przewodnim pracy jest chęć sprawdzenia w działaniu różnych konceptów struktur pamięciowych, które opisane zostaną w dalszej części pracy.

Problem został określony jako pytanie: Która z wybranych struktur pamięciowych w zadanych zmiennych warunkach okaże się najwydajniejsza dla różnych operacji?

1.2 Wybrane struktury pamięciowe

Do przeprowadzonych eksperymentów wybrane zostały następujące struktury:

  • Lista,
  • Słownik,
  • T-Drzewa;

Struktury dobrane zostały na względ na swoją różnorodność i chęć sprawdzenia w praktyce różnych podejść do operowania na danych.

Dokładny opis wybranych struktur znajduje się w rozdziale 2.

1.3 Cel pracy

Celem pracy jest analiza porównawcz wybranych struktur pamięciowych, w odniesieniu do serii testów, których zadaniem jest sprawdzenie szybkości danych rozwiązań, dla operacji:

  • dodawania,
  • odczytu,
  • odczytu sekwencyjnego,
  • aktualizacji,
  • usuwania,
  • kombinacji powyższych operacji.

Koncepty testów oparte zostały na propozycji zaprezentowanej w A Study of Index Structures for Main Memory Database Management Systems.

Jako hipotezę badawczą przypuszczamy największą wydajność struktur hashowych takich jak słownik dla operacji dodawania, odczytu pojedynczej wartości oraz usuwania, a także najlepszą wydajność T-Drzewa dla odczytu sekwencyjnego wartości w przedziale.

2 Implementacja baz danych opartych na strukturach pamięciowych

W sekcji tej znajduje się informacja odnośnie sposobu implementacji każdej ze struktur. Wszystkie struktury zostały zaimplementowane w języku Python.

2.1 Lista

Implementacja tej bazy opiera się na wbudowanej strukturze listy, której zadaniem jest przechowywanie wielu zmiennych w jednym obiekcie.

2.1.1 Dodawanie

def add(self, key: int, value: T) -> bool:
    for item in self.items:
        if item[0] == key:
            return False
    self.items.append((key, value))

Kod prezentujący metodę dodawania elementu do listy.

Metoda przyjmująca 2 argumenty: key (liczba całkowita) oraz value.

Operacja ta wykonywana jest na istniejącej bazie danych. Do bazy danych dodawana jest para (key, value) z unikalnym kluczem w postaci liczby całkowitej. Tuż po wywołaniu metody, baza danych sprawdzana jest pod kątem występowania klucza w bazie.

Jeżeli klucz znajduje się w bazie danych, operacja jest przerywana, zwrócone zostanie False, w przeciwnym wypadku para dodawana jest do bazy danych

2.1.2 Odczyt

def get(self, key: int) -> T:
    for item in self.items:
        if item[0] == key:
            return item[1]
    return None

Kod prezentujący metodę odczytującą element z listy.

Metoda przyjmująca 1 argument w postaci liczby całkowitej - key.

Odczytywanie z listy zaimplementowane jest za pomocą pętli for przeszukującej całą bazę danych. Pętla wykonywana jest do pierwszego wystąpienia poszukiwanego klucza.

Jeżeli podczas przeszukiwania listy klucz nie zostanie znaleziony, zwracane jest None, reprezentujące wartość pustą lub wartość, która nie istnieje.

2.1.3 Odczyt sekwencyjny

def get_range(self, key_from: int, key_to: int) -> list[T]:
    to_return = []
    for item in self.items:
        if key_from <= item[0] <= key_to:
            to_return.append(item[1])
    return to_return

Kod prezentujący metodę odczytujący sekwencje elementów z listy.

Metoda przyjmuje 2 argumenty - key_from oraz key_to, których postacią są 2 liczby całkowite.

Do operacji odczytu sekwencyjnego z listy wykorzystywana jest pętla for. Przeszukiwana jest zawsze cała lista w celu znalezienia wartości, dla kluczy z przedziału od key_from do key_to.

Wyniki zbierane są w tymczasową listę to_return, która jest zawsze zwracana - niezależnie czy jest pusta czy nie.

2.1.4 Aktualizacja

def update(self, key: int, new_value: T) -> bool:
    for item in self.items:
        if item[0] == key:
            index_to_update = self.items.index(item)
            self.items[index_to_update] = (key, new_value)
            return True
    return False

Kod prezentujący metodę aktualizacji elementu w liście.

Do poprawnego wywołania metody aktualizacji wymagane jest podanie 2 argumentów: klucza - key oraz nowej wartości - new_value.

Operacja aktualizowania wartości przy danym kluczu odbywa się za pomocą pętli for. Pętla wykonywana jest do pierwszego wystąpienia danego klucza, dla którego wartość value zostaje zmieniona przez wskazane new_value.

Jeżeli klucz nie znajduje się w bazie danych zwrócona zostanie wartość False.

2.1.5 Usuwanie

def delete(self, key: int) -> bool:
    for item in self.items:
        if item[0] == key:
            self.items.remove(item)
            return True
    return False

Kod prezentujący metodę usuwającą element z listy.

Metoda przyjmująca tylko 1 argument, czyli liczbę całkowitą key.

Operacja usuwania odbywa się za pomocą pętli for. Przeszukiwanie w celu znalezienia klucza wykonywane jest aż do znalezienia owego klucza. Tuż przed przerwaniem wykonywania pętli, para z danym kluczem zostaje usunięta, zwrócone zostanie True.

W przeciwnym wypadku, jeżeli para z danym kluczem nie istnieje metoda zwraca wartość False.

2.2 Słownik

Implementacja tej bazy opiera się na wbudowanej strukturze słownika (ang. dictionary), której zadaniem jest przechowywanie wielu par o postaci klucz-wartość w jednej zmiennej.

2.2.1 Dodawanie

def add(self, key: int, value: T) -> bool:
    if key in self.items.keys():
        return False
    self.items[key] = value

Kod prezentujący metodę dodającą element do słownika.

Metoda przyjmująca 2 argumenty: klucz (key) oraz wartość (value). Klucz jest unikalną wartością w postaci liczby całkowitej.

Dodawanie elementu do słownika rozpoczyna się od sprawdzenia czy klucz znajduje się w bazie danych. Jeśli tak, zwracana jest wartość False, w przeciwnym przypadku do klucza key przypisywana jest wartość value.

2.2.2 Odczyt

def get(self, key: int) -> T:
    return self.items.get(key)

Kod prezentujący metodę odczytującą element ze słownika.

Metoda przyjmuje 1 argument, czyli liczbę całkowitą jako key.

Pobierana i zwracana jest wartość dla danego klucza, jeżeli klucz nie znajduje się w słowniku, zwracane zostaje None.

2.2.3 Odczyt sekwencyjny

def get_range(self, key_from: int, key_to: int) -> list[T]:
    to_return = []
    for key in self.items.keys():
        if key_from <= key <= key_to:
            to_return.append(self.items[key])
    return to_return

Kod prezentujący metodę odczytującą sekwencje elementów ze słownika.

Metoda przyjmuje 2 argumenty w postaci liczb całkowitych: key_from, key_to, które tworzą przedział działania pętli for.

Przeszukiwany jest cały słownik w poszukiwaniu pasujących kluczy. Wszystkie znalezione wartości umieszczane są w liście to_return, która zawsze jest zwracana, nawet jeżeli jest pusta.

2.2.4 Aktualizacja

def update(self, key: int, new_value: T) -> bool:
    if key not in self.items.keys():
        return False
    self.items[key] = new_value

Kod prezentujący metodę aktualizującą elementy w słowniku.

Do poprawnego działania metody wymagane są 2 argumenty: klucz (key) w postaci liczby całkowitej oraz nową wartość (new_value).

Po wywołaniu metody, słownik sprawdzany jest pod kątem występowania danego klucza - aby przypadkiem nie utworzyć pary z kluczem, który wcześniej nie istniał. Po poprawnym zweryfikowaniu słownika, wartość dla klucza zostaje zastąpiona przez wartość new_value.

W przypadku, gdy klucz nie istnieje w słowniku, zwracana zostaje wartość False.

2.2.5 Usuwanie

def delete(self, key: int) -> bool:
    if key not in self.items.keys():
        return False
    self.items.pop(key)

Kod prezentujący metodę usuwającą element ze słownika.

Metoda do poprawnego działania wymaga podania 1 argumentu, czyli klucza (key) w postaci liczby całkowitej.

Na początku operacji słownik sprawdzany jest pod kątem występowania klucza, jeśli klucz znajduje się w bazie danych, jest usuwany. W przeciwnym wypadku zostaje zwrócona wartość False.

2.3 T-Drzewo

T-Drzewo zostało zaimplementowane w języku Python.

W tym celu została stworzona klasa Node, która odpowiada jednostce pojedynczego węzła w drzewie. Całość została stworzona na podstawie A Study of Index Structures for Main Memory Database Management Systems.

Jest to struktura drzewiasta wywarzona, której każdy wierzchołek zawiera wskaźnik do wierzchołka zawierającego wartości indeksu mniejsze od key_from po lewej oraz większe od key_to po prawej. Wewnętrznie przechowuje ona wartości dla indeksów pomiędzy key_from oraz key_to.

class Node:
    __slots__ = ('left', 'right', 'key_from', 'key_to', 'values')
 
    def __init__(self, key, value, node_size=100, left=None, right=None):
        self.left = left
        self.right = right
        self.key_from = key // node_size * node_size
        self.key_to = key // node_size * node_size + node_size - 1
        self.values = {key: value}

Kod prezentujący klasę węzła w T-Drzewie.

2.3.1 Dodawanie

def add(self, key: int, value: T) -> bool:
    if search(self.root, key) is not None:
        return False
    self.root = insert(self.root, key, value)
    self.size += 1
    self.check()
    
def insert(node, key, value):
    if node is None:
        return Node(key, value)
    if key < node.key_from:
        node.left = insert(node.left, key, value)
    elif key > node.key_to:
        node.right = insert(node.right, key, value)
    else:
        node.values[key] = value
    return node

Kod prezentujący metodę dodającą element do drzewa wraz z metodą pomocniczą.

def check(self):
    if depth(self.root.left) - depth(self.root.right) > 1:
        self.root = rotation_right(self.root)
    elif depth(self.root.right) - depth(self.root.left) > 1:
        self.root = rotation_left(self.root)
 
def depth(node):
    if node is None:
        return 0
    else:
        left_depth = depth(node.left)
        right_depth = depth(node.right)
 
        if left_depth > right_depth:
            return left_depth + 1
        else:
            return right_depth + 1
 
def rotation_right(node):
    y = node.left
    t = y.right
 
    y.right = node
    node.left = t
 
    return y
 
def rotation_left(node):
    y = node.right
    t = y.left
 
    y.left = node
    node.right = t
 
    return y

Kod reprezentujący implementacje metod pomocniczych służących do rotacji drzewa.

Metoda do poprawnego działania wymaga 2 argumentów: klucza (key) oraz wartości (value).

Dane dodawane są nawet do nieistniejącego drzewa, jeśli drzewo nie istnieje to przy pierwszej dodawanej wartości jest tworzone.

Na początku operacji drzewo jest przeszukiwane, by uniknąć próby dodania istniejącego klucza do drzewa - w przypadku, gdy klucz istnieje w bazie danych, zwrócona zostanie wartość False.

Następnie wartość jest już dodawana do drzewa według założeń drzewa w postaci wpisu do węzła. Każdy węzeł ma równy rozmiar i przechowuje równą liczbę wpisów w postaci par klucz-wartość. Dodatkowo atrybutami opisującymi węzeł są granice przedziału kluczy: key_from, key_to. Zaraz po dodaniu pary do drzewa, zwiększany jest licznik rozmiaru bazy danych oraz następuje sprawdzenie drzewa za pomocą metody check(), która ma na celu sprawdzenie możliwości rotacji drzewa w lewo, bądź w prawo.

2.3.2 Odczyt

def get(self, key: int) -> T:
    res = search(self.root, key)
    if res is not None:
        return res.values[key]
    return None
    
def search(root, key):
    if root is None:
        return root
    if root.key_from <= key <= root.key_to:
        if key in root.values:
            return root
    if root.key_from > key:
        return search(root.left, key)
    return search(root.right, key)

Kod reprezentujący implementację odczytywania wartości z drzewa wraz z metodą pomocniczą.

Wymaganiem metody jest 1 argument: klucz (key).

Wykorzystywany jest on do przeszukania drzewa w celu znalezienia wartości o podanym kluczu. Na początku szukany jest węzeł który zawiera dany klucz, przeszukiwanie odbywa się za pomocą wzdłużnego przechodzenia drzewa (pre-order). Gdy węzeł zostanie znaleziony, pobierana jest z niego wartość jeśli istnieje. Wartość ta zostaje zwrócona. W przeciwnym wypadku, jeśli nie zostanie znaleziony węzeł spełniający wymagania, zwracane jest None.

2.3.3 Odczyt sekwencyjny

def get_range(self, key_from: int, key_to: int) -> list[T]:
    result = []
    for key in range(key_from, key_to + 1):
        temp = search(self.root, key)
        if temp is not None:
            result += [[key, temp.values[key]]]
    return result

Kod reprezentujący implementację odczytywania sekwencji wartości z drzewa.

Metoda przyjmuje 2 argumenty: key_from oraz key_to, które jako liczby całkowite są skrajnymi wartościami przedziału kluczy.

Odczyt sekwencyjny odbywa się za pomocą zwykłego Odczytu, ale z dodatkiem pętli for, która odpowiada za pracę na przedziale liczbowym. Wszystkie znalezione pary umieszczane są w tymczasowej liście result, która niezależnie od rozmiaru, jest zwracana.

2.3.4 Aktualizacja

def update(self, key: int, new_value: T) -> bool:
    res = update(self.root, key, new_value)
    if res is None:
        return False
        
def update(root, key, new_value):
    if root is None:
        return root
    if root.key_from <= key <= root.key_to:
        if key in root.values:
            root.values[key] = new_value
            return root
    if root.key_to < key:
        return update(root.right, key, new_value)
    return update(root.left, key, new_value)

Kod reprezentujący implementację aktualizacje wartości drzewa wraz z metodą pomocniczą.

Do poprawnego działania wymagane jest podanie 2 argumentów: klucz (key) oraz nowa wartość (new_value).

Podobnie jak w przypadku operacji Odczytu, znalezienie węzła do zmiany odbywa się przez przechodzenie drzewa wzdłuż (pre-order). Po znalezieniu odpowiedniego węzła, sprawdzana jest obecność konkretnego klucza w węźle. Jeśli klucz znajduje się w węźle, następuje zmiana wartości na new_value.

W przeciwnym wypadku operacja jest przerywana i zwracana jest wartość None.

2.3.5 Usuwanie

def delete(self, key: int) -> bool:
    res = deleteNode(self.root, key)
    if not res[1]:
        return False
    self.size -= 1
    
def deleteNode(root, key, deleted=False):
    if root is None:
        return root, deleted
    if isinstance(root, tuple):
        r = root[0]
    else:
        r = root
    if (r.key_from <= key <= r.key_to) and (len(r.values) > 0):
        if key in r.values:
            del r.values[key]
            deleted = True
            if len(r.values) == 0:
                tmp = deleteNode(r, r.key_from)
                if tmp is not None:
                    r = tmp[0]
    else:
        if key < r.key_from:
            tmp = deleteNode(r.left, key)
            if tmp is not None:
                r.left = tmp[0]
        elif key > r.key_to:
            tmp = deleteNode(r.right, key)
            if tmp is not None:
                r.right = tmp[0]
        else:
            if r.left is None:
                temp = r.right
                r = None
                return temp, deleted
            elif r.right is None:
                temp = r.left
                r = None
                return temp, deleted
 
            temp = minValueNode(r.right)
            r.key = temp[0]
            r.right = deleteNode(r.right, temp[0])[0]
    return r, deleted

Kod reprezentujący implementację usuwania wartości z drzewa wraz z metodą pomocniczą.

Metoda do poprawnego działania wymaga 1 argumentu, czyli klucza (key).

Po rozpoczęciu operacji usuwania klucza z drzewa następuje wyszukiwanie odpowiedniego węzła przechowującego dany klucz.

Następnie, jeżeli klucz zostanie znaleziony sprawdzane są pary w węźle, by zweryfikować obecność klucza do usunięcia.

Po poprawnej weryfikacji klucz zostaje usunięty z węzła, po czym sprawdzany jest rozmiar węzła. Jeżeli rozmiar węzła jest równy 0, następuje usunięcie węzła z drzewa, w przeciwnym wypadku zwracana jest para składająca się z głównego węzła i flagi informującej o usunięciu klucza.

Za pomocą flagi sprawdzany jest status wykonania operacji, jeśli usuwanie powiodło się to rozmiar bazy danych jest zmniejszony o 1, jeśli nie zwracana jest wartość False.

3 Metodyka badań

W tym rozdziale zostanie opisana obrana metodologia badań uwzględniająca poszczególne operacje, środowisko oraz sposób przeprowadzenia badań.

3.1 Wybrane operacje

Do badań wybrano 6 różnych operacji:

  • Dodawanie - do istniejącej bazy danych dodano n różnych nowych wartości o kolejnych wartościach indeksu, rozpoczynających się od wartości większej o 1 od największej obecnie istniejących. Pod każdy z kluczy generowano losowo dane osoby (imię, nazwisko, numer PESEL, adres mailowy, numer telefonu, wiek oraz adres).

  • Odczyt - do odczytu wybierano każdorazowo losową wartość ze wszystkich wartości indeksu bazy danych.

  • Odczyt sekwencyjny - do odczytu wybierano każdorazowo losową wartość początkową przedziału. Na jej podstawie każdorazowo dokonano 100 odczytów sekwencyjnych wartości kluczy.

  • Aktualizacja - do aktualizacji wybierano każdorazowo losową wartość ze wszystkich wartości indeksu bazy danych, a następnie dokonywano ponownego generowania danych osoby.

  • Usuwanie - do usuwania wybrano każdorazowo losową wartość, od wartości minimalnej, do maksymalnej z bazy danych. Niektóre odczyty mogły próbować usunąć wartość nieistniejącą.

  • Połączenie operacji - operacja składająca się z łańcucha 600 operacji odczytu z całej bazy danych, 600 operacji dodania wartości o nowych indeksach wzorem operacji dodania oraz 600 operacji usunięcia dodanych przed chwilą danych.

3.2 Przeprowadzone badania

W celu uzyskania miarodajnych wyników, objęto poniższą metodologie badań.

Każda z operacji została wykonana 3000 razy pod rząd, w celu uniknięcia tzw. outlayerów, mierząc czas wykonania zbioru operacji. Pozwoliło to osiągnąć uśrednione czasy dla każdej z operacji. W czas operacji jest również wliczony losowy wybór wartości z przedziału zależnego od wielkości danych.

Sekwencje operacji zostały uruchomione na bazach danych z różną, początkową ilością danych. zaczynając na 10,000 rekordach, kończąc na 100,000 z krokiem 10,000.

W celu zminimalizowania wpływu usług uruchamianych przez system w tle niezależnie od użytkownika, generując outlayery, cały proces został wykonany 3 razy, pozwalając na uśrednienie wyników badań.

3.3 Opis środowiska

Środowisko do przeprowadzenia badań stanowi komputer wyposażony w:

  • Procesor Ryzen 5 3600
  • 16 GB pamięci DDR4 o taktowaniu 3200 MHz
  • System Windows 11 w wersji 21H2
  • Python w wersji 3.11.1

W ramach przeprowadzanych badań, nie dokonywano żadnych operacji na wyżej wymienionym systemie.

4 Wyniki badań

W tej sekcji zawiera się wizualizacja oraz opis wyników przeprowadzonych badań.

4.1 Dodawanie danych

Zauważyć można, że w procesie dodawania najwolniejsza jest baza danych oparta na liście, gdzie jej złożoność rośnie mniej-więcej liniowo.

Następna w kolejności jak chodzi o prędkość jest baza oparta na T-Drzewie dla węzła o wielkości 100, którego złożoność rożnie mniej więcej liniowo W przypadku dwóch pozostałych baz opartych na T-Drzewach zauważyć można, że rosną one bardzo powoli.

Najszybszą operację dodawania posiada baza oparta na słowniku, której to czas odczytu jest stały.

4.2 Odczyt losowy danych

Operacje odczytu losowego prezentują się podobie do operacji dodawania danych.

Najwolniejszy odczyt posiada struktura listowa, następnie struktury oparte na T-Drzewie, a najszybsza jest struktura oparta na słowniku, która to jest jedyna niezależna od wielkości bazy danych.

4.3 Odczyt sekwencyjny danych

Operacja odczytu sekwencyjnego na bazie opartej na słowniku jest najwolniejsza. Nieznacznie szybsza jest ta oparta na liście oraz na T-Drzewie z węzłem o wielkości 100.

Znacznie szybsze są struktury oparte na T-Drzewie z węzłami o wielkościach 500 oraz 1000.

Wszystkie struktury wykazały tutaj złożoność liniową.

4.4 Aktualizacja danych

Zdecydowanie najwolniejszą strukturą do tej operacji jest lista, której to złożoność rośnie liniowo.

Wszystkie pozostałe struktury wykonują tą operację znacznie szybciej. Jednak warto zauważyć, że poza listą, T-Drzewo z węzłem o wielkości 100 widocznie zależy od wielkości bazy danych.

4.5 Usuwanie danych

Usuwanie danych z listy zajmuje najwięcej czasu i rośnie ono liniowo.

Następna jest baza oparta na T-Drzewie o wielkości 100, 1000 oraz 500, które rosną logarytmicznie.

Najszybsze jest operowanie na strukturze słownika, które rośnie nieznacznie w zależności od wielkości bazy danych.

4.6 Połączenie operacji

Połączenie operacji prezentuje się analogicznie do wykresu operacji dodawania, gdzie operowanie na liście zajmuje najdłużej, następnie jest operowanie na T-Drzewie o węźle z wielkością 100, 1000, 500 oraz na słowniku.

5 Podsumowanie

Wyniki zaprezentowane w poprzedniej sekcji umożliwiają wyciągnięcie następujących wniosków.

W większości testów (w szczególności scenariuszach jak dodawanie, czy aktualizacja) widać główne wady listy, z uwagę na potrzebę przeszukiwania struktury. Sam początkowy czas niezbędny do wykonywania operacji jest stosunkowo wysoki względem pozostałych struktur.

Struktura słownika prezentuje się najlepiej pod względem wydajności dla wszystkich operacji poza odczytem sekwencyjnym. Wynika to z tego, że jest ona oparta na stałym czasie dostępu poprzed obliczanie lokalizacji na podstawie podanego klucza, jako struktura hashowa.

T-Drzewo w istotnym stopniu zależy od wielkości bazy danych, z uwagi na to, że jest to struktura drzewiasta. Operacje takie dodawanie czy usuwanie posiadają narzut czasu który wynika z potrzeby balansowania struktury, a jedynym narzutem czasu dla odczytu i aktualizacji jest samo schodzenie niżej w strukturze bazy danych. Czyni to operacje odczytu niezwykle efektywną.

Dla odczytu sekwencyjnego widać zbliżone wyniki dla listy, słownika i t-drzewa w wariancie 100-węzłowym. Fakt znalezienia się w tym gronie słownika tłumaczy to, że w tym przypadku generalna zaleta polegająca na przeszukiwaniu struktury zostaje zniwelowana z uwagi na charakter operacji, w której ułożone kolejno po sobie dane faworyzują struktury takie jak lista, czy T-Drzewo, których to kolejne dane są łatwo dostępne oraz ułożone obok siebie w pamięci.

Z używanych wariantów T-Drzew widać znaczące różnice, zwłaszcza między wariantem 100-węzłowym, resztą. Wynika to głównie z wielkości węzłów na poziom, powodujące częste potrzeby tworzenia nowych poziomów, a w wyniku ciągłego kopiowania danych i samych operacji na strukturze, wysoki czas operacji.

Ciekawą zależność można natomiast zaobserwować między wersją 500 i 1000 węzłową. Przypuszczalnie powodem takiego stanu rzeczy jest problem z odpowiednim wyważeniem przypadających węzłów, co może być tematem przyszłych badań.

W przypadku bazy danych o wielkości 100,000 elementów, przy węźle o rozmiarze 1000, w dużej mierze przegląd elementów zaczyna momentami przypominać przegląd listy o stałej długości 1000. Czym większy jest węzeł, tym dłużej zajmuje jego przegląd, natomiast podowuje on zmniejszenie samej struktury T-Drzewa poprzez zmniejszenie liczby węzłów. Dodatkowo zmniejsza się częstość równoważenia drzewa, gdyż potrzebujemy dodać więcej elementów, żeby być zmuszeni na dodanie kolejnego węzła.

Dane uzyskane w ramach eksperymentu popierają hipotezę badawczą, gdzie faktycznie najszybszy odczyt, zapis pojedynczych wartości oraz usuwanie jest najszybsze w strukturach hash’owych takich jak słownik, a odczyt w przedziale najszybszy jest w T-Drzewie.

6 Literatura

  1. Hector Garcia-Molina, Kenneth Salem, Main Memory Database Systems: An Overview, IEEE Transactions on Knowledge and Data Engineering Vol.4 No.6 December 1992
  2. Tobin J. Lehman, Michael J. Carey, A Study of Index Structures for Main Memory Database Management Systems, Computer Sciences Department, University of Wisconsin-Madison, 25 August 1986